数据结构与算法 |
您所在的位置：网站首页 › 数据结构与算法 串 › 数据结构与算法 |
|
文章目录
1 串匹配概述
2 蛮力算法
2.1 蛮力算法版本A
2.2 蛮力算法版本B
2.3 蛮力算法测试
3 KMP算法
3.1 KMP主算法
3.2 构造next表
3.3 KMP算法测试程序
4 BM算法
4.1 BM主算法
4.2 坏字符策略与bc表
4.3 好后缀策略与gs表
4.4 BM算法测试
5 Karp-Rabin算法
6 Sunday算法
参考材料
1 串匹配概述
字符串匹配有多种形式，包括模式检测( pattern detection)，模式定位(pattern location)，模式计数(pattern counting)，模式枚举(pattern enumration)。 2 蛮力算法蛮力算法是最直接最直觉的方法，可以作为改进的基础。 2.1 蛮力算法版本A //brute-force-A.h #include int matchA( char* P, char* T ){ //串匹配算法（Brute-force-1) size_t n = strlen( T ), i = 0; size_t m = strlen( P ), j = 0; while ( j //不匹配则文本串回退,模式串复位 i -= j - 1; j = 0; } return i - j; } 2.2 蛮力算法版本B //brute-force-B.h #include int matchB( char* P, char* T ){ //串匹配算法（Brute-force-2) size_t n = strlen( T ), i = 0; size_t m = strlen( P ), j ; for( i = 0; i if( T[i + j] != P[j] ) break;//失配则右移再做一轮比对 } if( j >= m ) break; //找到匹配子串 } return i; } 2.3 蛮力算法测试蛮力算法的测试程序如下，可见匹配成功时，版本A与版本B都会返回模式串在文本串中的位置。串匹配失败时，版本1返回大于n-m，版本2返回n-m+1。 /* * test program on string matching * author@Ripples * 20200807 */ #include "brute-force-A.h" #include "brute-force-B.h" #include using namespace std; int main(){ //初始化模式串与文本串 char P[] = "structure"; char Y[] = "alo"; char T[] = |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |